package leetcode.leetcode_hot100;

import java.util.Arrays;

public class T0079 {
    class Solution {
        public boolean exist(char[][] board, String word) {
            int h = board.length, w = board[0].length;
            boolean[][] visited = new boolean[h][w];
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    boolean flag = check(board, visited, i, j, word, 0);
                    if (flag) {
                        return true;
                    }
                }
            }
            return false;
        }

        public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
            if (board[i][j] != s.charAt(k)) {
                return false;
            } else if (k == s.length() - 1) {
                return true;
            }
            visited[i][j] = true;
            int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            boolean result = false;
            for (int[] dir : directions) {
                int newi = i + dir[0], newj = j + dir[1];
                if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                    if (!visited[newi][newj]) {
                        boolean flag = check(board, visited, newi, newj, s, k + 1);
                        if (flag) {
                            result = true;
                            break;
                        }
                    }
                }
            }
            visited[i][j] = false;
            return result;
        }
    }
    class Solution2 {
        char[] words;
        char[][] board;
        int[][] visited;
        int m,n;
        public boolean exist(char[][] board, String word) {
            if(board==null||board.length==0||word==null||word.equals(""))
                return false;
            words=word.toCharArray();
            this.board=board;
            m=board.length;
            n=board[0].length;
            visited=new int[m][n];
            for(int i=0;i<m;i++)
                Arrays.fill(visited[i],0);
            boolean res=false;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    res=dfs(i,j,0);
                    if(res==true)
                        return true;
                }
            }
            return res;
        }
        public boolean dfs(int x,int y,int index){
            if(index==words.length)//找到结果，返回true
                return true;
            if(x<0||y<0||x>=m||y>=n)//越界，返回false
                return false;
            if(board[x][y]!=words[index])//不是想要的值，返回false
                return false;
            if(visited[x][y]==1)//已访问过，返回false
                return false;

            boolean res=false;
            visited[x][y]=1;//标记为已访问过
            //遍历上下左右
            res=dfs(x-1,y,index+1)||dfs(x+1,y,index+1)||dfs(x,y-1,index+1)||dfs(x,y+1,index+1);
            if(res==true){
                return true;
            }
            visited[x][y]=0;//重置标记，回溯
            return res;
        }
    }

}
